package YuanFuDao2;

import java.util.ArrayList;

import java.util.List;

/**
 * 八皇后
 * 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，
 * 其中每个皇后都不同行、不同列，也不在对角线上。
 * 这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
 */
public class Main14 {

    public static void main(String[] args) {
        List<List<String>> res = solveNQueens(4);
        System.out.println(res.toString());
    }

    public static List<List<String>> solveNQueens(int n) {
        char[][] grid = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = '.';
            }
        }
        List<List<String>> res = new ArrayList<>();
        boolean[] col = new boolean[n];
        boolean[] dg = new boolean[n+n-1];    //共有2*N-1种对角线
        boolean[] udg = new boolean[n+n-1];   //共有2*N-1种反对角线


        dfs(0,n,grid,col,dg,udg,res);

        return res;
    }


    public  static void dfs(int h,int n,char[][] grid,boolean[] col,boolean[] dg,boolean[] udg,List<List<String>> res){
        if(h == n){
            List<String> list = new ArrayList<>();
            for (int i = 0; i < grid.length; i++) {
                list.add(new String(grid[i]));
            }
            res.add(list);
            return;
        }
        for (int j = 0; j < n; j++) {
            if(!col[j] && !dg[n-1-h+j] && !udg[h+j]){
                grid[h][j] = 'Q';
                col[j] = true;
                //dg[n-h+j] = true;  //行和列的差   //对角线为y = x + n  (n为一个有关上下文的数)
                dg[n-1-h+j] = true;
                udg[h+j] = true;   //行和列的和   //反对角线为y = -x + m （m为一个有关上下文的数）
                dfs(h+1,n,grid,col,dg,udg,res);
                grid[h][j] = '.';
                col[j] = false;
                dg[n-1-h+j] = false;
                udg[h+j] = false;
            }
        }
    }

}
